I. Field of the Invention
The present invention is directed to telecommunications. More particularly, the present invention is directed to methods and systems for synchronizing Access Points within a Wireless Local Area Network. However, aspects of the invention may be equally applicable in other scenarios as well.
II. Description of Related Art
Over the recent years, the market for wireless communications has enjoyed tremendous growth. Wireless technology now reaches or is capable of reaching virtually every location on the face of the earth. One reason for this tremendous growth has been the IEEE wireless Local Area Network (“LAN”) standard 802.11.
An 802.11 LAN is based on a cellular architecture where the system is subdivided into cells. Each cell or Basic Server Set (“BSS”) is controlled by a Base Station. This Base Station is often referred to as an Access Point (“AP”). Even though a wireless LAN may be formed by a single cell, with a single Access Point, and in certain arrangements it can also work without an Access Point. Generally, however, most LAN installations will comprise several cells. The Access Points connected through some kind of backbone called Distribution System (“DS”), typically Ethernet, and in some cases wireless itself.
The whole interconnected Wireless LAN including the different cells, there respective Access Points and the Distribution System, is seen to the upper layers of the OSI model, as a single 802 network, and is called in the Standard an Extended Service Set (“ESS”).
The standard also defines the concept of a Portal where a Portal is a device that interconnects between an 802.11 and another 802 LAN. This concept is an abstract description of the functionality of a “translation bridge.” As any 802.x protocol, the 802.11x protocol covers that MAC and Physical Layer, the Standard currently defines a single MAC which interacts with three PHYs (all of them running at 1 and 2 Mbit/s up to 54 Mbit/s). Frequency hopping spread spectrum in the 2.4 Ghz Band, Direct Frequency Spread Spectrum in the 2.4 GHz Band, and Infrared. Beyond the standard functionality usually performed by MAC Layers, the 802.11 MAC performs other functions that are typically related to upper layer protocols, such as Fragmentation, Packet Retransmissions, and Acknowledges. The MAC Layer defines two access methods, the Distributed Coordination Function and the Point Coordination Function.
The basic access mechanism, called Distributed Coordination Function, is a Carrier Sense Multiple Access with Collision Avoidance mechanism (“CSMA/CA”). CSMA protocols are known, where the most popular is the Ethernet, which is a CSMA/CD protocol (CD standing for Collision Detection).
With a CSMA protocol, a station desiring to transmit senses the medium. If the medium is busy (i.e, some other station is transmitting), then the station will defer its transmission to a later time. If the medium is sensed free or available for transmission, then the station is allowed to transmit. These kinds of protocols are effective when the medium is not heavily loaded, since it allows stations to transmit with minimum delay. However, there is a chance of stations transmitting at the same time (collision), caused by the fact that the stations sensed the medium free and decided to transmit at once.
These collision situations should be identified, so that the MAC layer can retransmit the packet by itself and not by upper layer, which would cause significant delay. In the Ethernet case, this collision is recognized by the transmitting stations which go to a retransmission phase base on an exponential random backoff algorithm. While these Collision Detection mechanisms are a good idea on a wired LAN, such Collision Detection mechanisms are typically difficult to implement in a Wireless LAN environment. For example, implementing a Wireless LAN based Collision Detection Mechanism would require the implementation of a Full Duplex radio, capable of transmitting and receiving at once. Such a full duplex approach would also tend to increase the complexity and price of the system significantly.
In addition, on a wireless environment one cannot assume that all stations hear each other. This is generally a basic assumption of the Collision Detection scheme. The fact that a station willing to transmit and senses the medium free, does not necessarily mean that the medium is free around the receiver area. In order to overcome these two concerns, the 802.11 uses a Collision Avoidance mechanism together with a Positive Acknowledge scheme. In this Positive Acknowledge scheme, a station willing to transmit senses the medium is busy then it defers transmission. If the medium is free for a specified time (called DIFS, Distributed Inter Frame Space), then the station is allowed to transmit.
A receiving station will check the CRC of the received packet and send an acknowledgment packet (“ACK”). Receipt of the ACK will indicate to the transmitter that no collision occurred. If the sender does not receive the acknowledgment then it will retransmit the fragment until it gets acknowledged or thrown away after a given number of retransmissions.
In order to reduce the probability of two stations colliding because they cannot hear each other, 802.11 defines a Virtual Carrier Sense mechanism. A station willing to transmit a packet will first transmit a short control packet called RTS (Request to Send). The RTS includes the source, destination, and the duration of the following transaction (i.e., the packet and the respective ACK). The destination station responds (if the medium is free) with a response control Packet called CTS (“Clear to Send”). The CTS will include the same duration information.
Stations receiving either the RTS and/or the CTS, will set their Virtual Carrier Sense indicator (called NAV, for Network Allocation Vector), for the given duration, and will use this information together with the Physical Carrier Sense when sensing the medium. This mechanism reduces the probability of a collision on the receiver area by a station that is “hidden” from the transmitter, to the short duration of the RTS transmission, because the stations will hear the CTS and “reserve” the medium as busy until the end of the transaction. The duration information on the RTS also protects the transmitter area from collisions during the ACK (by stations that are out of range from the acknowledging stations).
Because RTS and CTS are short frames, it also reduces the overhead of collisions, since these are recognized faster than it would be recognized if the whole packet was to be transmitted, (this is true if the packet is significantly bigger than the RTS, so the standard allows for short packets to be transmitted without the RTS/CTS transaction, and this is controlled per station by a parameter called RTS Threshold.
Typical LAN protocols use packets of several hundred of bytes (e.g., Ethernet longest packet could be up to 1518 bytes long), on a Wireless LAN environment there are some reasons why it would be preferable to use smaller packets. For example, because of the higher Bit Error Rate of a radio link, the probability of a packet to get corrupted increases with the packet size. In addition, in the case of packet corruption (either because of collision or noise), the smaller the packet the less overhead it causes to retransmit it. In addition, on Frequency Hopping system, the medium is interrupted periodically for hopping (in our case every 20 milliseconds), so the smaller the packet, the smaller the chance that the transmission will be proposed to after the dwell time.
The mechanism is a simple Send-and-Wait algorithm, where the transmitting station is not allowed to transmit a new fragment until one of the following happens: receives an ACK for the said fragment or decides that the fragment was retransmitted too many times and drops the whole frame.
Exponential Backoff is a method that attempts to resolve contention between different stations willing to access a medium. The method requires each station to choose a Random Number n between 0 and a given number. Then, wait for this number of Slots before accessing the medium, and then checking whether a different station has accessed the medium before. The Slot Time is defined in such a way that a station will be capable of determining if another station has accessed the medium at the beginning of the previous slot. This reduces the collision probability by half.
Exponential Backoff means that each time the station chooses a slot and happens to collide, it will increase the maximum number of the random selection exponentially. 802.11 defines Exponential Backoff Algorithm that will be executed in the following case. Where, if when the station senses the medium before the first transmission of a packet, and the medium is busy.
When a station wants to access an existing BSS (either after power-up, sleep mode, or just entering the BSS area), the station needs to receive synchronization information from an Access Point (or from the other stations when in an ad-hoc mode). The station can get this information by one of two means: passive scanning or active scanning. First, it may get this information by passive scanning. In the passive scanning case, the station waits to receive a beacon frame from the AP. The beacon frame is a periodic frame sent by the AP with synchronization information.
Alternatively, active scanning may be used where a station tries to find an AP by transmitting Probe Request Frames, and waiting for Probe Response from the AP. Either of these methods may be chosen according to the power consumption/performance itself.
Once the station has found an AP, and the station has decided to join the AP's BSS, the station will go through the Authentication Process. This Process is an interchange of information between the AP and the station, where each side proves the knowledge of a given password.
When a station is authenticated, then the station will start the Association Process. This process is the exchange of information about the stations and BSS capabilities, and which allows the DSS (the set of APs to know about the current position of the station). Only after the association process is completed, a station is capable of transmitting and receiving data frames.
Stations need to keep synchronization since this is needed for keeping hopping synchronized, and other functions like Power Saving. On an infrastructure BSS this is performed by all the stations updating their clocks according to the AP's clock. This synchronization occurs as the AP transmits periodic frames called Beacon Frames. These Beacon Frames contain the value of the AP's clock on the moment of transmission. Note that this is the moment when the transmission really occurs, and not when it is put in the queue for transmission, since the Beacon Frame is transmitted using the rules of CSMA, the transmission may be delayed significantly.
The receiving stations check the value of their clock at the receiving moment and correct it to keep synchronizing with the AP's clock. This prevents clock drifting which could cause loss of synchronization after a couple hours of operation.
In a typical wireless network, such as a Wireless Local Area Network (“WLAN”) system, each Access Point (“AP”) will have it's own internal clock. Each independent clock will also define the Time Division Multiplexing (“TDMA”) timing of the SSID area that this AP covers. Consequently, this means that all AP's, provided in a certain WLAN SSID area, will be not be synchronized. Consequently, these unsynchronized BSS cells may interfere with one another. These unsynchronized BSS cells will interfere with each other even if they are operating on the same channels or alternatively adjacent yet different channels.
In an effort to reduce such interference concerns, it is generally known that the overall system throughput may be improved when there is at least beacon synchronization and scheduling between all stations in the ESS environment. Existing mechanisms like fragmentation, data rate back-off, adaptive contention window threshold, as other mechanisms, will help improve the system throughput to a certain extent. However, there is, therefore, a general need for a method and system for synchronizing WLAN APs. There is also a general need for a method and system for synchronizing WLAN APs while also improving system capacity and QoS by utilizing AP synchronization and beacon scheduling.